#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a,ll b){
    if(a%b==0)return b;
    else return gcd(b,a%b);
}

void solve() {
    ll a,b,k;
    cin>>a>>b>>k;
    if(a<=k&&b<=k){
        cout<<1<<'\n';
        return;
    }
    ll t=gcd(a,b);
    // cout<<t<<'\n';
    // cout<<(a/t)<<' '<<(b/t)<<'\n';
    if(t>1&&(a/t)<=k&&(b/t)<=k){
        cout<<1<<'\n';
        return;
    }else{
        cout<<2<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
}